查看原文
其他

腾讯三面:缺失的QQ号码是哪个?

The following article is from 涛歌依旧 Author 点击关注👉👉

点击关注公众号,一周多次包邮送书

来源:经授权转自 涛歌依旧(ID:ai_taogeyijiu_2021)

作者:涛歌依旧


今天,我们来看一道有趣的腾讯三面的面试题,有一定难度和技巧。可以坦白地说,如果没有提前进行类似训练,那就不太可能现场做对这道题目,一起来看看:

腾讯题目:假设QQ号码的取值范围是(0, max_unsigned_int),现有n个QQ号码,求出其中缺失的最小的QQ号码。要求时间复杂度为O(n),空间复杂度为O(1).


熟悉LeetCode的朋友自然眼前一亮,这道题是咱们的老熟人啊,一起来看看LeetCode上的题目,并以LeetCode题目为例,详细讲解具体的思路和解法。

LeetCode题目: 给定一个整数数组,请找出其中缺失的最小的正整数,要求时间复杂度为O(n),空间复杂度为O(1),输入输出的具体示例如下面表格所示:

输入数组a
输出
[1, 2, 0]3
[3, 4, 1, -1]2
[6, 7, 8, 12]1


我们先来分析一下:

  • 假设a中的n个元素占满了1~n, 那么缺失的最小正整数就是n+1.

  • 假设a中的n个元素没有完全占满1~n, 那么缺失的最小正整数必然是1~n之间的某个数。

综合可知:缺失的最小正整数必然在区间[1, n+1]中。这是一个非常重要的结论

基于该结论,我们来循序渐进地分析和讲解这道LeetCode题目,一起来看看吧。


一. 暴力破解

暴力算法很简单,直接遍历区间[1, n+1],然后判断元素是否在a中。此时,时间复杂度是O(n*n),空间复杂度为O(1).  

显然,无法通过面试


二. 哈希算法

从暴力破解的过程可知,这无非就是一个查找的问题,那么可以考虑用哈希表。具体如下:
把a数组用哈希表来记录,然后直接去遍历区间[1, n+1],就可以判断元素是否在哈希表中。
此时,时间复杂度和空间复杂度都是O(n).
显然,无法通过面试


三. 巧妙标记

我们参考哈希算法,并在标记元素是否存在时做巧妙优化。

以a = [3, 4, 1, -1]为例,n = 4,过程如下:

原始数组

[3, 4, 1, -1]
非正数改为n+1[3, 4, 1, 5]
3存在,用a[3-1]的负号来标识
[3, 4, -1, 5]
4存在,用a[4-1]的负号来标识
[3, 4, -1, -5]
1存在,用a[1-1]的负号来标识
[-3, 4, -1, -5]
a[x-1]=4,是正数,故x必然不存在
x=2便是缺失的最小正整数

可以看到,在记录元素x是否存在时,使用的是a[x - 1]的符号,其中,x的区间是[1, n]. 该算法的时间复杂度是O(n),空间复杂度是O(1).
这种标记方式是非常巧妙的,可以通过面试,而且确实不太容易想到。既然算法的步骤确定了,那么对应的程序就相对简单了,一起来看下:
package mainimport "fmt"
func abs(x int) int { if x < 0 { return -x }
return x}
func solution(a []int) int { n := len(a) for i := 0; i < n; i++ { if a[i] <= 0 { a[i] = n + 1 } }
for i := 0; i < n; i++ { num := abs(a[i]) if num <= n { a[num - 1] = -abs(a[num - 1]) } }
for i := 0; i < n; i++ { if a[i] > 0 { return i + 1 } }
return n + 1}
func main() { a := []int{3, 4, 1, -1} fmt.Println(solution(a))}
结果为2,刚好就是缺失的最小正整数。


四. 置换归位

我们再看看更加直观的想法。对于数组a的元素i,如果i在区间[1, n]中,可通过置换归位,把i放到a[i-1]处,如下:

输入数组a

置换目标
[1, 2, 0][1, 2, 0]
[3, 4, 1, -1][1, -1, 3, 4]
[6, 7, 8, 12][6, 7, 8, 12]


置换后,再次遍历a, 如果a[x-1]和x不相等,那么,x肯定就是缺失的最小正整数,如下:

置换目标

x(缺失的最小正整数)
[1, 2, 0]3
[1, -1, 3, 4]2
[6, 7, 8, 12]1


该算法的时间复杂度是O(n),空间复杂度是O(1),可以通过面试。程序很简单,如下:
package mainimport "fmt"
func solution(a []int) int { n := len(a) for i := 0; i < n; i++ { // 注意:下面这里要用for, 而不是if. for a[i] > 0 && a[i] <= n && a[a[i]-1] != a[i] { a[a[i]-1], a[i] = a[i], a[a[i]-1] } }
for i := 0; i < n; i++ { if a[i] != i + 1 { return i + 1 } }
return n + 1}
func main() { a := []int{3, 4, 1, -1} fmt.Println(solution(a))}

结果为2,刚好就是缺失的最小正整数。

·················END·················

推荐阅读

•  俄罗斯手机品牌欲抛弃安卓转用鸿蒙,华为回应•  因屏蔽广告,这款受欢迎的小众浏览器凉了•  一个悄然成为世界最流行的操作系统•  Windows新功能太“社死”!教你一键快速禁用•  网信办出手,这个 App 遭殃了!!•  百度慌了,这款第三方下载神器又复活了!!(文末送书)•  这 14 个 VSCode 插件,让你写代码如同神一般•  火狐阻止中国用户下载uBo/AdGuard等多款知名广告拦截扩展(文末送书)


👇更多内容请点击👇

  

  大疆再遭制裁,设计软件Figma断供!中国工业软件如何应对全面封禁? 


您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存